package com.berchen.算法.动态规划算法;

import java.util.Arrays;

/**
 * 背包问题
 * 有一个背包 容量4 KG
 * 有三个物品
 *  1  重 1 KG 1500 元
 *  2  重 4 KG 3000 元
 *  3  重 3 KG 2000 元
 *
 *  找到一种背包装物品的组合  使得背包中装的物品的价格最大  但是容量不能超过背包容量
 *
 */
public class KnapsackProblem {

    public static void main(String[] args) {

        int[] w = {1, 4, 3};    // 物品的重量
        int[] v = {1500, 3000, 2000};   // 物品的价格
        int m = 4;   // 背包的容量
        int n = v.length;    // 物品的个数


        // 创建二维数组
        // bg[i][j] 表示 在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] bg = new int[n + 1][m + 1];   // 列索引表示的是背包的容量

        // 为了记录放入商品的情况， 我们定义一个二维数组
        int[][] path = new int[n + 1][m + 1];


        // 初始化第一行第一列
        for (int i = 0; i < bg.length; i++) {
            bg[i][0] = 0;
        }
        for (int j = 0; j < bg[0].length; j++) {
            bg[0][j] = 0;
        }
        // 初始背包值
        for (int i = 0; i < bg.length; i++) {
            System.out.println(Arrays.toString(bg[i]));
        }

        // 填写背包 找到最优解
        for (int i = 1; i < bg.length; i++) {   // 不处理第一行
            for (int j = 1; j < bg[i].length; j++) {   // 不处理第一列
                // 公式
                if (w[i - 1] > j) {
                    bg[i][j] = bg[i - 1][j];
                } else {
//                    bg[i][j]=Math.max(bg[i-1][j],v[i-1]+bg[i-1][j-w[i-1]]);
                    // 为了记录商品存放到背包的情况  我们不能简单使用上面的  我们需要使用if else
                    if (bg[i - 1][j] >= v[i - 1] + bg[i - 1][j - w[i - 1]]) {
                        bg[i][j] = bg[i - 1][j];
                    } else {
                        bg[i][j] = v[i - 1] + bg[i - 1][j - w[i - 1]];
                        // 将当前的情况记录到path
                        path[i][j]=1;
                    }
                }
            }
        }
        System.out.println("============");
        // 分配后的背包值
        for (int i = 0; i < bg.length; i++) {
            System.out.println(Arrays.toString(bg[i]));
        }
        System.out.println("path");
        for (int i = 0; i < path.length; i++) {
            System.out.println(Arrays.toString(path[i]));
        }
        System.out.println("===========最优解：");
        // 从path中输出
        int i= path.length-1;
        int j=path[0].length-1;
        while (i>0&&j>0){
            if(path[i][j]==1){
                System.out.printf("第%d个商品放入到背包\n",i);
                j-=w[i-1];
            }
            i--;
        }


    }
}
